import tool.ListNode;

import java.time.temporal.Temporal;
import java.util.HashSet;
import java.util.Set;

/**
 * @Description:  链表相交
 * 给你两个单链表的头节点 headA 和 headB ，
 * 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * 图示两个链表在节点 c1 开始相交：
 *
 * @Date:Create in 18:46  2022/6/30
 */
public class getIntersectionNode02_07 {


    //双指针法
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0,lenB = 0;

        while(curA != null){
            lenA++;
            curA = curA.next;
        }
        while(curB != null){
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;

        //让curA成为较长链表的头
        if(lenB>lenA){
            int templen = lenA;
            ListNode tempCur = curA;

            lenA = lenB;
            lenB = templen;

            curA = curB;
            curB = tempCur;
        }

        int gap = lenA - lenB;
        while(gap>0){
            gap--;
            curA = curA.next;
        }

        while(curA!=null){
            if(curA==curB) return curA;
            curA = curA.next;
            curB = curB.next;
        }
        return null;

    }

    //哈希表法
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<ListNode>();
        ListNode cur = headA;
        while(cur!=null){
            set.add(cur);
            cur=cur.next;
        }

        cur = headB;
        while (cur!=null){
            if(set.contains(cur)){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

}
